package leetCode.solution;

/**
 * 最大矩形 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
 * 
 * @author jerry
 * @ClassName: Solution85
 * @Description:TODO(描述这个类的作用)
 * @date 2022年11月15日 下午6:09:34
 */
public class Solution85 {

	public static void main(String[] args) {
		char aa[][] = new char[][] {{'1','0','1','1','1'},{'0','1','0','1','0'},{'1','1','0','1','1'},{'1','1','0','1','1'},{'0','1','1','1','1'}};
		System.out.println(new Solution85().maximalRectangle(aa));
	}

	public int maximalRectangle(char[][] matrix) {
		int rowNum = matrix.length;
		int colNum = matrix[0].length;

		int[][] tmp = new int[rowNum][colNum];

		for (int i = 0; i < rowNum; i++) {
			for (int j = 0; j < colNum; j++) {
				if (matrix[i][j] == '1') {
					tmp[i][j] = j == 0 ? 1 : tmp[i][j - 1] + 1;
				}
			}
		}

		int area = 0;
		for (int i = 0; i < rowNum; i++) {
			for (int j = 0; j < colNum; j++) {
				if (matrix[i][j] == '0') {
					continue;
				}
				int minWidth = tmp[i][j];
				for (int k = i; k >=0; k--) {
					if (matrix[k][j] == '0') break;
					minWidth = Math.min(tmp[k][j], minWidth);
					area = Math.max(area, (i - k + 1) * minWidth);
				}
			}
		}
		return area;
	}
}
